package algorithms.leaning.class21;

import common.util.MyUtil;

/**
 * 给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角
 * 沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和
 * 返回最小距离累加和
 *
 * @author guichang
 * @date 2021/6/21
 */

@SuppressWarnings("all")
public class Code1_动态规划_最小路径和 {

    public static void main(String[] args) {
        int[][] matrix = {
                {3, 7, 8, 7},
                {1, 2, 6, 4},
                {10, 9, 8, 9},
                {8, 1, 2, 1}
        };
        MyUtil.print(minPath(matrix));
        MyUtil.print(minPathDp(matrix));
        MyUtil.print(minPathDpCompress(matrix));
    }

    /**
     * 方法一 暴力递归
     */
    public static int minPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        return process(matrix, 0, 0);
    }

    /**
     * 从(x,y)开始到右下角的最小路径
     */
    private static int process(int[][] matrix, int x, int y) {
        // 无效
        if (x == matrix.length || y == matrix[0].length) {
            return Integer.MAX_VALUE;
        }
        // 走到了最右下角
        if (x == matrix.length - 1 && y == matrix[0].length - 1) {
            return matrix[x][y];
        }
        // 往右走
        int right = process(matrix, x, y + 1);
        right = right == Integer.MAX_VALUE ? right : (matrix[x][y] + right);
        // 往下走
        int down = process(matrix, x + 1, y);
        down = down == Integer.MAX_VALUE ? down : (matrix[x][y] + down);
        // 取最小值
        return Math.min(right, down);
    }

    /**
     * 方法二 dp数组
     */
    public static int minPathDp(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int R = matrix.length;
        int C = matrix[0].length;
        int[][] dp = new int[R][C];
        dp[R - 1][C - 1] = matrix[R - 1][C - 1];
        // 填充最后一列
        for (int i = R - 2; i >= 0; i--) {
            dp[i][C - 1] = matrix[i][C - 1] + dp[i + 1][C - 1];
        }
        // 填充最后一行
        for (int j = C - 2; j >= 0; j--) {
            dp[R - 1][j] = matrix[R - 1][j] + dp[R - 1][j + 1];
        }
        // 从右下角开始
        for (int i = R - 2; i >= 0; i--) {
            for (int j = C - 2; j >= 0; j--) {
                dp[i][j] = matrix[i][j] + Math.min(dp[i][j + 1], dp[i + 1][j]);
            }
        }
        return dp[0][0];
    }

    /**
     * 方法三 空间压缩，仅使用单数组
     */
    public static int minPathDpCompress(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int R = matrix.length;
        int C = matrix[0].length;
        // 一行的数据
        int[] dp = new int[C];
        // 初始化最后一行
        dp[C - 1] = matrix[R - 1][C - 1];
        for (int j = C - 2; j >= 0; j--) {
            dp[j] = dp[j + 1] + matrix[R - 1][j];
        }
        // 往上填
        for (int i = R - 2; i >= 0; i--) {
            dp[C - 1] += matrix[i][C - 1];
            for (int j = R - 2; j >= 0; j--) {
                dp[j] = Math.min(dp[j + 1], dp[j]) + matrix[i][j];
            }
        }
        return dp[0];
    }


}